package com.dyz.leetcode._05_sort;

import java.util.Arrays;
import java.util.Random;

public class _75_sortColors {
    // 自带排序
    public void sortColors(int[] nums) {

        Arrays.sort(nums);

    }

    //手写快排
    public void sortColors1(int[] nums){

        quickSort(nums, 0, nums.length-1);
    }

    public void quickSort(int[] nums, int lo, int hi){
        if(lo>=hi){return;}

        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index-1);
        quickSort(nums, index+1, hi);

    }

    private int partition(int[] nums, int lo, int hi) {
        int mid = new Random().nextInt(hi-lo+1)+lo;// 随机选一个作为 pivot
        //与最后一个交换
        swap(nums, mid, hi);
        //
        int pivot = nums[hi];
        int less = lo;
        int great = lo;
        for(;great<=hi-1; great++){
            if(pivot>nums[great]){
                swap(nums, less, great);
                less++;
            }
        }
        swap(nums, less, hi);
        return less;
    }


    public void swap(int[] nums, int l, int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
